package exercises.newcoder.solution;

import java.util.Scanner;

/**
 * <a href="https://www.nowcoder.com/study/live/717/7/4">
 * 第4节 随堂习题-机器人到达指定位置方法数</a>
 *
 * @author or2
 * @Description 假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种。由于方案数可能比较大，所以答案需要对1e9+7取模。
 * @create 2021年09月09日 时间: 21:01
 */
public class WalkDP {

    //    不变常量
    static final int MOD = (int) (1E9) + 7;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        总格子数目 - N
        int totalPositionNums = scanner.nextInt();
//        起始位置 - M
        int startPos = scanner.nextInt();
//        剩余步数 - K
        int rest = scanner.nextInt();
//        目的地 - P
        int endPos = scanner.nextInt();
        if (totalPositionNums < 2 || endPos < 1 || totalPositionNums < endPos) {
            System.out.println(0);
        }
        System.out.println(walkDP(startPos, rest, totalPositionNums, endPos));
    }

    public static int walkDP(int start, int rest, int totalPositionNums, int endPos) {
        if (totalPositionNums < start || rest < 1) {
            return 0;
        }

        int[][] dp = new int[totalPositionNums][rest + 1];
        dp[endPos - 1][0] = 1;

        for (int j = 1; j < rest + 1; j++) {
            for (int i = 0; i < totalPositionNums; i++) {
                if (i == 0) {
                    dp[i][j] = dp[i + 1][j - 1];
                    continue;
                }
                if (i == totalPositionNums - 1) {
                    dp[i][j] = dp[i - 1][j - 1];
                    continue;
                }
                dp[i][j] = dp[i - 1][j - 1] + dp[i + 1][j - 1];
                dp[i][j] %= MOD;
            }
        }

        return dp[start - 1][rest];
    }
}

